package algorithm.dfs;

import algorithm.TreeNode;
import org.apache.hadoop.yarn.webapp.hamlet.Hamlet;

import java.util.ArrayList;
import java.util.List;

/**
 * @author cyt
 * @create 2020-08-25 11:27
 */
public class T257 {
    public static void main(String[] args) {

    }

    /**
     * 给定一个二叉树，返回所有从根节点到叶子节点的路径。
     *
     * 此时碰到叶子节点可以直接返回值， 在非叶子节点情况下就记录下结果， 然后对左右子树也同样操作，确定访问整个树
     *
     */
    List ans = new ArrayList<String>();

    public List<String> binaryTreePaths(TreeNode root) {
        dfs(root, "");
        return ans;
    }

    public void dfs(TreeNode root, String sb) {
        /**
         * ["1->2->5", "1->3"]
         */
        if (root == null) {
            return;
        }
        sb += root.val;
        /**
         * 叶子节点， 此时找到一个解
         */
        if (root.left == null && root.right == null) {
            ans.add(sb);
        } else {
            dfs(root.left, sb + "->");
            dfs(root.right, sb + "->");
        }
    }
}
